{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Dota2 Senate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #queue #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #队列 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: predictPartyVictory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #Dota2 参议院"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Dota2 的世界里有两个阵营：<code>Radiant</code>（天辉）和&nbsp;<code>Dire</code>（夜魇）</p>\n",
    "\n",
    "<p>Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 <strong>一 </strong>项：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>禁止一名参议员的权利</strong>：参议员可以让另一位参议员在这一轮和随后的几轮中丧失<strong> 所有的权利 </strong>。</li>\n",
    "\t<li><strong>宣布胜利</strong>：如果参议员发现有权利投票的参议员都是 <strong>同一个阵营的</strong> ，他可以宣布胜利并决定在游戏中的有关变化。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>senate</code> 代表每个参议员的阵营。字母 <code>'R'</code> 和 <code>'D'</code>分别代表了&nbsp;<code>Radiant</code>（天辉）和&nbsp;<code>Dire</code>（夜魇）。然后，如果有 <code>n</code> 个参议员，给定字符串的大小将是&nbsp;<code>n</code>。</p>\n",
    "\n",
    "<p>以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。</p>\n",
    "\n",
    "<p>假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是&nbsp;<code>\"Radiant\"</code> 或 <code>\"Dire\"</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>senate = \"RD\"\n",
    "<strong>输出：</strong>\"Radiant\"\n",
    "<strong>解释：\n",
    "</strong><code>第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。\n",
    "这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。\n",
    "第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人</code>。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>senate = \"RDD\"\n",
    "<strong>输出：</strong>\"Dire\"\n",
    "<strong>解释：</strong>\n",
    "第 1 轮时，第一个<code>来自 Radiant 阵营的</code>参议员可以使用第一项权利禁止第二个参议员的权利。\n",
    "<code>这一轮中，</code>第二个<code>来自 Dire 阵营的</code>参议员会将被跳过，因为他的权利被禁止了。\n",
    "<code>这一轮中，</code>第三个<code>来自 Dire 阵营的</code>参议员可以使用他的第一项权利禁止第一个参议员的权利。\n",
    "因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == senate.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>senate[i]</code> 为 <code>'R'</code> 或 <code>'D'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [dota2-senate](https://leetcode.cn/problems/dota2-senate/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [dota2-senate](https://leetcode.cn/problems/dota2-senate/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"RD\"', '\"RDD\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate):\n",
    "        \"\"\"\n",
    "        :type senate: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        R_B,D_B=0,0\n",
    "        N,R,D = len(senate),senate.count('R'),senate.count('D')\n",
    "        live = [True]*N\n",
    "        i=-1\n",
    "        while(1):\n",
    "            i=(i+1)%N\n",
    "            if not live[i]:\n",
    "                continue\n",
    "            \n",
    "            if R==0:\n",
    "                return 'Dire'\n",
    "            elif D==0:\n",
    "                return 'Radiant'\n",
    "            \n",
    "            if senate[i]=='R':\n",
    "                if R_B>0:\n",
    "                    R_B-=1\n",
    "                    R-=1\n",
    "                    live[i]=False\n",
    "                else:\n",
    "                    D_B+=1\n",
    "            else:\n",
    "                if D_B>0:\n",
    "                    D_B-=1\n",
    "                    D-=1\n",
    "                    live[i]=False\n",
    "                else:\n",
    "                    R_B+=1\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: 'str') -> 'str':\n",
    "        score = 0\n",
    "        while len(senate) > 1:\n",
    "            temp = ''\n",
    "            for i in range(len(senate)):\n",
    "                if 'R' == senate[i]:\n",
    "                    if score >= 0:\n",
    "                        temp += 'R'\n",
    "                    score += 1\n",
    "                elif 'D' == senate[i]:\n",
    "                    if score <= 0:\n",
    "                        temp += 'D'\n",
    "                    score -= 1\n",
    "            senate = temp\n",
    "            if 'R' not in senate or 'D' not in senate:\n",
    "                return 'Radiant' if senate[0] == 'R' else 'Dire'\n",
    "            \n",
    "        return 'Radiant' if senate[0] == 'R' else 'Dire'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate):\n",
    "        \"\"\"\n",
    "        :type senate: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        senate = list(senate)\n",
    "        i = len(senate)\n",
    "        while True:\n",
    "            if 'R' not in senate:\n",
    "                return 'Dire'\n",
    "            elif 'D' not in senate:\n",
    "                return 'Radiant'\n",
    "            if senate[0] == '0':\n",
    "                senate.append(senate[0])\n",
    "                senate = senate[1:]\n",
    "                continue\n",
    "            for j in range(1,i):\n",
    "                if senate[j] != '0' and senate[0] != senate[j]:\n",
    "                    senate[j] = '0'\n",
    "                    break\n",
    "            senate.append(senate[0])\n",
    "            senate = senate[1:]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate):\n",
    "        \"\"\"\n",
    "        :type senate: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not senate:\n",
    "            return \"\"\n",
    "        \n",
    "        q1 = Queue()\n",
    "        q2 = Queue()\n",
    "        r = 1\n",
    "        d = 1\n",
    "        pre = ''\n",
    "        flag = True\n",
    "        \n",
    "        def judge(s, q, r, d, cnt_r, cnt_d):\n",
    "            \n",
    "            if s == 'R':\n",
    "                if not d:\n",
    "                    r += 1\n",
    "                    q.put('R')\n",
    "                    cnt_r += 1\n",
    "                else:\n",
    "                    d -= 1\n",
    "            else:\n",
    "                if not r:\n",
    "                    d += 1\n",
    "                    q.put('D')\n",
    "                    cnt_d += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "            \n",
    "            return cnt_r, cnt_d, r, d\n",
    "        \n",
    "        cnt_r = cnt_d = 1 \n",
    "        r = d = 0\n",
    "        while cnt_r and cnt_d:\n",
    "            cnt_r = cnt_d = 0\n",
    "            \n",
    "            if q1.empty() and q2.empty():\n",
    "                for s in senate:\n",
    "                    # print(s)\n",
    "                    cnt_r, cnt_d, r, d = judge(s, q1, r, d, cnt_r, cnt_d)\n",
    "                    # print(cnt_r, cnt_d, r, d)\n",
    "            elif q1.empty():\n",
    "                while not q2.empty():\n",
    "                    s = q2.get()\n",
    "                    cnt_r, cnt_d, r, d = judge(s, q1, r, d, cnt_r, cnt_d)\n",
    "            elif q2.empty():\n",
    "                while not q1.empty():\n",
    "                    s = q1.get()\n",
    "                    cnt_r, cnt_d, r, d = judge(s, q2, r, d, cnt_r, cnt_d)\n",
    "                    \n",
    "        \n",
    "        if cnt_r == 0:\n",
    "            return \"Dire\"\n",
    "        else:\n",
    "            return \"Radiant\"\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate):\n",
    "        \"\"\"\n",
    "        :type senate: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        senate = list(senate)\n",
    "        print(senate)\n",
    "        dc = Counter(senate)\n",
    "        cr, cd = dc[\"R\"], dc[\"D\"]\n",
    "        kr, kd = 0, 0\n",
    "        while cr > 0 and cd > 0:\n",
    "            t = senate.pop(0)\n",
    "            if t == 'R':\n",
    "                if kr > 0:\n",
    "                    kr -= 1\n",
    "                    cr -= 1\n",
    "                else:\n",
    "                    kd += 1\n",
    "                    senate.append('R')\n",
    "            else:\n",
    "                if kd > 0:\n",
    "                    kd -= 1\n",
    "                    cd -= 1\n",
    "                else:\n",
    "                    kr += 1\n",
    "                    senate.append('D')\n",
    "        return \"Radiant\" if cr > 0 else \"Dire\"\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate):\n",
    "        \"\"\"\n",
    "        :type senate: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        senate = list(senate)\n",
    "        i = len(senate)\n",
    "        while True:\n",
    "            if 'R' not in senate:\n",
    "                return 'Dire'\n",
    "            elif 'D' not in senate:\n",
    "                return 'Radiant'\n",
    "            for j in range(1,i):\n",
    "                if senate[0] != senate[j]:\n",
    "                    senate = senate[0:j] + senate[j+1:]\n",
    "                    break\n",
    "            senate.append(senate[0])\n",
    "            senate = senate[1:]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate):\n",
    "        \"\"\"\n",
    "        :type senate: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        from collections import deque\n",
    "        R = deque()\n",
    "        D = deque()\n",
    "        n = len(senate)\n",
    "        for idx, alp in enumerate(senate):\n",
    "            if alp == \"R\":\n",
    "                R.appendleft(idx)\n",
    "            else:\n",
    "                D.appendleft(idx)\n",
    "        # print(R)\n",
    "        # print(D)\n",
    "        while R and D:\n",
    "            idx_R = R.pop()\n",
    "            idx_D = D.pop()\n",
    "            if idx_R < idx_D:\n",
    "                R.appendleft(idx_R + n)\n",
    "            else:\n",
    "                D.appendleft(idx_D + n)\n",
    "        return \"Radiant\" if len(R) > len(D) else \"Dire\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate):\n",
    "        \"\"\"\n",
    "        :type senate: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        senate=list(senate)\n",
    "        while True:\n",
    "            for i in range(len(senate)):\n",
    "                if senate[i]=='D':\n",
    "                    try:\n",
    "                        try:\n",
    "                            senate[senate.index('R',i)] = senate[senate.index('R')] + '0'\n",
    "                        except:\n",
    "                            senate[senate.index('R')] = senate[senate.index('R')] + '0'\n",
    "                    except:\n",
    "                        return 'Dire'\n",
    "                elif senate[i]=='R':\n",
    "                    try:\n",
    "                        try:\n",
    "                            senate[senate.index('D',i)] = senate[senate.index('D')] + '0'\n",
    "                        except:\n",
    "                            senate[senate.index('D')] = senate[senate.index('D')] + '0'\n",
    "                    except:\n",
    "                        return 'Radiant'\n",
    "                elif senate[i]=='R0':\n",
    "                    continue\n",
    "                else:\n",
    "                    continue\n",
    "        if 'D' in senate:\n",
    "            return 'Dire'\n",
    "        else:\n",
    "            return 'Radiant'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def predictPartyVictory(self, senate):\n",
    "        \"\"\"\n",
    "        :type senate: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        q_r, q_d = collections.deque(), collections.deque()\n",
    "        n = len(senate)\n",
    "        for i, s in enumerate(senate):\n",
    "            if s == \"R\":\n",
    "                q_r.append(i)\n",
    "            else:\n",
    "                q_d.append(i)\n",
    "        while q_r and q_d:\n",
    "            r = q_r.popleft()\n",
    "            d = q_d.popleft()\n",
    "            if r < d:\n",
    "                q_r.append(r + n)\n",
    "            else:\n",
    "                q_d.append(d + n)\n",
    "        return \"Radiant\" if q_r else \"Dire\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        \n",
    "        def senateDR(string , m,n):  \n",
    "              \n",
    "            countD = m\n",
    "            countR = n\n",
    "            res = []\n",
    "            i = 0\n",
    "            numd= 0\n",
    "            numr=0\n",
    "            for i in range(len(string)):\n",
    "                if string[i] == \"D\": \n",
    "                    numd = numd+1\n",
    "\n",
    "                    if numd == len(string):\n",
    "                        return \"Dire\"       \n",
    "                    if countR > 0:\n",
    "                        countR = countR -1\n",
    "                        continue\n",
    "                    else:\n",
    "                        countD = countD +1\n",
    "                        res.append(\"D\")\n",
    "                    \n",
    "                \n",
    "                elif string[i] == \"R\" :\n",
    "                    numr = numr+1\n",
    "\n",
    "                    if numr == len(string):\n",
    "                        return \"Radiant\"\n",
    "                    \n",
    "                    if countD > 0:\n",
    "                        countD = countD -1\n",
    "                        continue\n",
    "                    else:\n",
    "                        countR = countR +1     \n",
    "                        res.append(\"R\") \n",
    "\n",
    "            \n",
    "            return senateDR(res , countD,countR)\n",
    "        \n",
    "        return senateDR(senate, 0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        senate = list(senate)\n",
    "        if not senate:\n",
    "            return ''\n",
    "\n",
    "        i = 0\n",
    "        slen = len(senate)\n",
    "        while i < slen:\n",
    "            s = senate[i]\n",
    "            slen -= 1\n",
    "            if s == 'R':\n",
    "                if 'D' in senate[i:]:\n",
    "                    idx = senate.index('D', i)\n",
    "                    senate.pop(idx)\n",
    "                elif 'D' in senate[:i]:\n",
    "                    idx = senate.index('D')\n",
    "                    senate.pop(idx)\n",
    "                else:\n",
    "                    return 'Radiant'\n",
    "            else:\n",
    "                if 'R' in senate[i:]:\n",
    "                    idx = senate.index('R', i)\n",
    "                    senate.pop(idx)\n",
    "                elif 'R' in senate[:i]:\n",
    "                    idx = senate.index('R')\n",
    "                    senate.pop(idx)\n",
    "                else:\n",
    "                    return 'Dire'\n",
    "            i += 1\n",
    "\n",
    "        return self.predictPartyVictory(senate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        senates = [s for s in senate]\n",
    "        part_r, part_d, i = 0, 0, 0\n",
    "        while i < len(senates) and part_d != len(senates) and part_r != len(senates):\n",
    "            if senates[i] == \"R\" and part_d == 0:\n",
    "                part_r += 1\n",
    "                i = i + 1 if i < len(senates) - 1 else 0\n",
    "            elif senates[i] == \"D\" and part_r == 0:\n",
    "                part_d += 1\n",
    "                i = i + 1 if i < len(senates) - 1 else 0\n",
    "            elif senates[i] == \"R\" and part_d > 0:\n",
    "                senates.pop(i)\n",
    "                part_d -= 1\n",
    "                i = i if i < len(senates) else 0\n",
    "            elif senates[i] == \"D\" and part_r > 0:\n",
    "                senates.pop(i)\n",
    "                part_r -= 1\n",
    "                i = i if i < len(senates) else 0\n",
    "        return \"Dire\" if part_d != 0 else \"Radiant\"\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "\n",
    "        init_r_val = 0\n",
    "        last_senate = senate\n",
    "        while True:\n",
    "            all_same = True\n",
    "            head_senate = last_senate[0]\n",
    "            next_senate = []\n",
    "            for sen in last_senate:\n",
    "                if sen != head_senate:\n",
    "                    all_same = False\n",
    "                if sen == \"R\":\n",
    "                    if init_r_val >= 0:\n",
    "                        next_senate.append(sen)\n",
    "                    init_r_val += 1\n",
    "                if sen == \"D\":\n",
    "                    if init_r_val <= 0:\n",
    "                        next_senate.append(sen)\n",
    "                    init_r_val += -1\n",
    "\n",
    "            if all_same:\n",
    "                if init_r_val > 0:\n",
    "                    return \"Radiant\"\n",
    "                if init_r_val < 0:\n",
    "                    return \"Dire\"\n",
    "                raise Exception(\"Unexpect data\")\n",
    "            last_senate = next_senate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        counter = collections.Counter(senate)\n",
    "        ban_counter = collections.Counter()\n",
    "        q = collections.deque()\n",
    "        for s in senate:\n",
    "            q.append(s)\n",
    "\n",
    "        while counter['R'] > 0 and counter['D'] > 0:\n",
    "            s = q.popleft()\n",
    "            if ban_counter[s] > 0:\n",
    "               ban_counter[s] -= 1\n",
    "               counter[s] -= 1\n",
    "            else:\n",
    "                if s == 'R': ban_counter['D'] += 1\n",
    "                else: ban_counter['R'] += 1\n",
    "                q.append(s)\n",
    "        return 'Radiant' if counter['R'] > 0 else 'Dire'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        nextR, nextD = 0, 0; mx = []\n",
    "        size = len(senate); i = 0\n",
    "        for s in senate:\n",
    "            if s == 'R':\n",
    "                mx.append(1)\n",
    "            else:\n",
    "                mx.append(2)\n",
    "        def ban(v):\n",
    "            nonlocal nextR, nextD, size, i\n",
    "            ix = (i + 1) % size\n",
    "            while ix != i and mx[ix] != v:\n",
    "                ix = (ix + 1) % size\n",
    "            if ix == i:\n",
    "                return True\n",
    "            mx[ix] = 0\n",
    "        while True:\n",
    "            if mx[i] == 1:\n",
    "                if ban(2):\n",
    "                    return 'Radiant'\n",
    "            elif mx[i] == 2:\n",
    "                if ban(1):\n",
    "                    return 'Dire'\n",
    "            i = (i + 1) % size\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        Rnumber = 0 # R阵营总人数\n",
    "        Dnumber = 0 # D阵营总人数\n",
    "        curBanR = 0 # R阵营当前被ban\n",
    "        curBanD = 0 # D阵营当前被ban\n",
    "        totalBanR = 0 #R阵营被ban总数\n",
    "        totalBanD = 0 #D阵营被ban总数\n",
    "        flag = True\n",
    "        chars = list(senate)\n",
    "        while True:\n",
    "            for i in range(len(chars)):\n",
    "                cur = chars[i]\n",
    "                if cur == \"R\":\n",
    "                    if flag:\n",
    "                        Rnumber += 1\n",
    "                    if curBanR == 0:\n",
    "                        curBanD += 1\n",
    "                        totalBanD += 1\n",
    "                        if totalBanD == Dnumber and not flag:\n",
    "                            return \"Radiant\"\n",
    "                    else:\n",
    "                        curBanR -= 1\n",
    "                        chars[i] = 'r'\n",
    "\n",
    "                elif cur == \"D\":\n",
    "                    if flag:\n",
    "                        Dnumber += 1\n",
    "                    if curBanD == 0:\n",
    "                        curBanR += 1\n",
    "                        totalBanR += 1\n",
    "                        if totalBanD == Dnumber and not flag:\n",
    "                            return \"Dire\"\n",
    "                    else:\n",
    "                        curBanD -= 1\n",
    "                        chars[i] = 'd'\n",
    "            flag = False\n",
    "            if totalBanD >= Dnumber:\n",
    "                return \"Radiant\"\n",
    "            if totalBanR >= Rnumber:\n",
    "                return \"Dire\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        this_round = list(senate)\n",
    "        r = d = 1\n",
    "        while r and d:\n",
    "            next_round = []\n",
    "            free_r = free_d = r = d = 0\n",
    "            #r, d = 0, 0\n",
    "            for c in this_round:\n",
    "                if c == 'R':\n",
    "                    if free_d > 0:\n",
    "                        free_d -= 1 #Killed by last 'D'\n",
    "                    else:\n",
    "                        free_r += 1\n",
    "                        r += 1\n",
    "                        next_round.append('R')\n",
    "                if c == 'D':\n",
    "                    if free_r > 0:\n",
    "                        free_r -= 1 # Killed by last 'R'\n",
    "                    else:\n",
    "                        free_d += 1 \n",
    "                        d += 1\n",
    "                        next_round.append('D')\n",
    "            while free_r > 0 and d > 0:\n",
    "                next_round.remove('D')\n",
    "                free_r -= 1\n",
    "                d -= 1\n",
    "            while free_d > 0 and r > 0:\n",
    "                next_round.remove('R')\n",
    "                free_d -= 1\n",
    "                r -= 1\n",
    "\n",
    "            print(next_round)\n",
    "            this_round = next_round\n",
    "        if r == 0:\n",
    "            return 'Dire'\n",
    "        return 'Radiant'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        self.result = []\n",
    "        def predictPartyVictory_copy(senate_list):\n",
    "            senate_left = []\n",
    "            if senate_list.count('D') == 0 or senate_list.count('R') == 0:\n",
    "                # print(senate_list)\n",
    "                #print(11111111)\n",
    "                #print(senate_list)\n",
    "                self.result = senate_list\n",
    "                return\n",
    "            else:\n",
    "                for i in range(len(senate_list)):\n",
    "                    if senate_list[i] == 'R' and 'D' in senate_list:\n",
    "                        if 'D' in senate_list[i+1:]:\n",
    "                            senate_list[senate_list[i + 1:].index('D') + i + 1] = 0\n",
    "                        else:\n",
    "                            senate_list[senate_list.index('D')] = 0\n",
    "                    elif senate_list[i] == 0:\n",
    "                        continue\n",
    "                    elif senate_list[i] == 'D' and 'R' in senate_list:\n",
    "                        #print(111111111)\n",
    "                        if 'R' in senate_list[i + 1:]:\n",
    "                            senate_list[senate_list[i+1:].index('R') + i + 1] = 0\n",
    "                           # print(senate_list)\n",
    "                        else:\n",
    "                            senate_list[senate_list.index('R')] = 0\n",
    "                for i in senate_list:\n",
    "                    if i != 0:\n",
    "                        senate_left.append(i)\n",
    "                #print(senate_left)\n",
    "                predictPartyVictory_copy(senate_left)\n",
    "        senate_list = list(senate)\n",
    "        predictPartyVictory_copy(senate_list)\n",
    "        if 'R' in self.result:\n",
    "            return 'Radiant'\n",
    "        else:\n",
    "            return 'Dire'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        \n",
    "        hs = {}\n",
    "        r = senate.count('R')\n",
    "        d = senate.count('D')\n",
    "        if r == 0:\n",
    "            return 'Dire'\n",
    "        if d == 0:\n",
    "            return 'Radiant'\n",
    "        \n",
    "        n = len(senate)\n",
    "        while True:\n",
    "            for i in range(n):\n",
    "                if i in hs:\n",
    "                    continue\n",
    "                \n",
    "                if senate[i] == 'D':\n",
    "                    r -= 1\n",
    "                    if r == 0:\n",
    "                        return 'Dire'\n",
    "                    tmp = i+1\n",
    "                    if tmp == n:\n",
    "                        tmp = 0\n",
    "                    while senate[tmp] == 'D' or tmp in hs:\n",
    "                        tmp += 1\n",
    "                        if tmp == n:\n",
    "                            tmp = 0\n",
    "                    hs[tmp] = 1\n",
    "\n",
    "                elif senate[i] == 'R':\n",
    "                    d -= 1\n",
    "                    if d == 0:\n",
    "                        return 'Radiant'\n",
    "                    tmp = i+1\n",
    "                    if tmp == n:\n",
    "                        tmp = 0\n",
    "                    while senate[tmp] == 'R' or tmp in hs:\n",
    "                        tmp += 1\n",
    "                        if tmp == n:\n",
    "                            tmp = 0\n",
    "                    hs[tmp] = 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        n = len(senate)\n",
    "        from collections import deque\n",
    "\n",
    "        Rq = deque()\n",
    "        Dq = deque()\n",
    "        for i, sen in enumerate(senate):\n",
    "            if sen == 'R':\n",
    "                Rq.append((i,sen))\n",
    "            if sen == 'D':\n",
    "                Dq.append((i,sen))\n",
    "        \n",
    "        while Dq and Rq:\n",
    "            if Dq[0][0] < Rq[0][0]:\n",
    "                Rq.popleft()\n",
    "                tmp1,tmp2 = Dq.popleft()\n",
    "                Dq.append((tmp1 + n, tmp2))\n",
    "            else:\n",
    "                Dq.popleft()\n",
    "                tmp1,tmp2 = Rq.popleft()\n",
    "                Rq.append((tmp1 + n, tmp2))\n",
    "        if Rq:\n",
    "            return 'Radiant'\n",
    "        if Dq:\n",
    "            return 'Dire'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        d = {\"R\": 0, \"D\": 0}\n",
    "        d2 = {\"R\": \"D\", \"D\": \"R\"}\n",
    "        while True:\n",
    "            new = \"\"\n",
    "            for i in senate:\n",
    "                if d[i]:\n",
    "                    d[i] -= 1\n",
    "                else:\n",
    "                    d[d2[i]] += 1\n",
    "                    new += i\n",
    "            senate = new\n",
    "            a, b = senate.count(\"R\"), senate.count(\"D\")\n",
    "            if a == 0:\n",
    "                return \"Dire\"\n",
    "            if b == 0:\n",
    "                return \"Radiant\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "         # R = true表示本轮循环结束后，字符串里依然有R。D同理\n",
    "        R , D = True, True\n",
    "\n",
    "        # 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭R\n",
    "        flag = 0\n",
    "\n",
    "        senate = list(senate)\n",
    "        while R and D: # 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了\n",
    "            R = False\n",
    "            D = False\n",
    "            for i in range(len(senate)) :\n",
    "                if senate[i] == 'R' :\n",
    "                    if flag < 0: senate[i] = '0' # 消灭R，R此时为false\n",
    "                    else: R = True # 如果没被消灭，本轮循环结束有R\n",
    "                    flag += 1\n",
    "                if senate[i] == 'D':\n",
    "                    if flag > 0: senate[i] = '0'\n",
    "                    else: D = True\n",
    "                    flag -= 1\n",
    "        # 循环结束之后，R和D只能有一个为true\n",
    "        return \"Radiant\" if R else \"Dire\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        senate = list(senate)\n",
    "        R = True\n",
    "        D = True\n",
    "        flag = 0 # 表示当前flag>0表示R在D前出现，flag<0表示D在R前出现\n",
    "        while R and D:\n",
    "            R = False\n",
    "            D = False\n",
    "            for i in range(len(senate)):\n",
    "                if senate[i] == 'R':\n",
    "                    if flag >= 0:\n",
    "                        R = True\n",
    "                    else:\n",
    "                        senate[i] = '0'\n",
    "                    flag += 1\n",
    "                if senate[i] == 'D':\n",
    "                    if flag <= 0:\n",
    "                        D = True\n",
    "                    else:\n",
    "                        senate[i] = '0'\n",
    "                    flag -= 1\n",
    "        return 'Radiant' if R else 'Dire'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        from queue import Queue\n",
    "        rq = Queue()\n",
    "        dq = Queue()\n",
    "        n = len(senate)\n",
    "        for i in range(len(senate)):\n",
    "            if senate[i] == 'R':\n",
    "                rq.put(i)\n",
    "            else:\n",
    "                dq.put(i)\n",
    "\n",
    "        while not rq.empty() and not dq.empty():\n",
    "            re = rq.queue.popleft()\n",
    "            de = dq.queue.popleft()\n",
    "            if re < de:\n",
    "                rq.put(re + n)\n",
    "            else:\n",
    "                dq.put(de + n)\n",
    "        if dq.empty():\n",
    "            return \"Radiant\"\n",
    "        else:\n",
    "            return \"Dire\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        n = len(senate)\n",
    "        radiant = collections.deque()\n",
    "        dire = collections.deque()\n",
    "        \n",
    "        for i, ch in enumerate(senate):\n",
    "            if ch == \"R\":\n",
    "                radiant.append(i)\n",
    "            else:\n",
    "                dire.append(i)\n",
    "        \n",
    "        while radiant and dire:\n",
    "            if radiant[0] < dire[0]:\n",
    "                radiant.append(radiant[0] + n)\n",
    "            else:\n",
    "                dire.append(dire[0] + n)\n",
    "            radiant.popleft()\n",
    "            dire.popleft()\n",
    "        \n",
    "        return \"Radiant\" if radiant else \"Dire\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        senate_list = list(senate)\n",
    "        r_senate_index = [i for i, s in enumerate(senate_list) if s == 'R']\n",
    "        d_senate_index = [i for i, s in enumerate(senate_list) if s == 'D']\n",
    "        n = len(senate)\n",
    "        if not r_senate_index:\n",
    "            return 'Dire'\n",
    "        if not d_senate_index:\n",
    "            return 'Radiant'\n",
    "        while True:\n",
    "            r0 = r_senate_index[0]\n",
    "            d0 = d_senate_index[0]\n",
    "\n",
    "            if r0 < d0:\n",
    "                d_senate_index.pop(0)\n",
    "                r_senate_index.append(r_senate_index.pop(0)+n)\n",
    "            else:\n",
    "                r_senate_index.pop(0)\n",
    "                d_senate_index.append(d_senate_index.pop(0)+n)\n",
    "\n",
    "            if len(d_senate_index) == 0:\n",
    "                return \"Radiant\"\n",
    "            if len(r_senate_index) == 0:\n",
    "                return \"Dire\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        R , D = True, True\n",
    "        flag = 0\n",
    "\n",
    "        senate = list(senate)\n",
    "        while R and D: \n",
    "            R = False\n",
    "            D = False\n",
    "            for i in range(len(senate)) :\n",
    "                if senate[i] == 'R' :\n",
    "                    if flag < 0: senate[i] = '0' # 消灭R，R此时为false\n",
    "                    else: R = True # 如果没被消灭，本轮循环结束有R\n",
    "                    flag += 1\n",
    "                if senate[i] == 'D':\n",
    "                    if flag > 0: senate[i] = '0'\n",
    "                    else: D = True\n",
    "                    flag -= 1\n",
    "                    # 循环结束之后，R和D只能有一个为true\n",
    "        return \"Radiant\" if R else \"Dire\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "\n",
    "        vic = deque()\n",
    "        sen = deque(senate)\n",
    "\n",
    "        while sen:\n",
    "            if not vic:\n",
    "                vic.append(sen.popleft())\n",
    "            else:\n",
    "                if vic[0] != sen[0]:\n",
    "                    sen.popleft()\n",
    "                    sen.append(vic.popleft())\n",
    "                else:\n",
    "                    vic.append(sen.popleft())\n",
    "\n",
    "        if vic[0] is 'R': \n",
    "            return \"Radiant\"\n",
    "        else:\n",
    "            return \"Dire\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        R, D = True, True        \n",
    "        flag = 0\n",
    "        senate = list(senate)\n",
    "        while R and D:\n",
    "            R = False\n",
    "            D = False\n",
    "            for i in range(len(senate)):\n",
    "                if senate[i] == 'R':\n",
    "                    if flag < 0: senate[i] = '0'\n",
    "                    else: R = True\n",
    "                    flag += 1\n",
    "                if senate[i] == 'D':\n",
    "                    if flag > 0: senate[i] = '0'\n",
    "                    else: D = True\n",
    "                    flag -= 1\n",
    "        return 'Radiant' if R else 'Dire'            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def predictPartyVictory(self, senate: str) -> str:\n",
    "        n = len(senate)\n",
    "        rs = collections.deque()\n",
    "        ds = collections.deque()\n",
    "        for i, s in enumerate(senate):\n",
    "            if s == \"R\":\n",
    "                rs.append(i)\n",
    "            else:\n",
    "                ds.append(i)\n",
    "        while rs and ds:\n",
    "            if rs[0] < ds[0]:\n",
    "                ds.popleft()\n",
    "                r = rs.popleft()\n",
    "                rs.append(r + n)\n",
    "            else:\n",
    "                rs.popleft()\n",
    "                d = ds.popleft()\n",
    "                ds.append(d + n)\n",
    "        return \"Radiant\" if rs else \"Dire\"\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
